import math
import random
 
# 计算两个城市之间的距离
def distance(city1, city2):
    return math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
 
# 计算路径的总长度
def path_length(path, cities):
    length = 0
    for i in range(len(path) - 1):
        length += distance(cities[path[i]], cities[path[i+1]])
    length += distance(cities[path[-1]], cities[path[0]])
    return length
 
# 生成一个随机的路径
def generate_path(num_cities):
    path = list(range(num_cities))
    random.shuffle(path)
    return path
 
# 模拟退火算法
def simulated_annealing(cities, max_temperature, cooling_rate):
    # 初始温度
    temperature = max_temperature
    # 初始路径
    path = generate_path(len(cities))
    # 初始路径长度
    length = path_length(path, cities)
    # 模拟退火算法
    temperature = max_temperature
    while temperature > 1:
        for _ in range(100):
            # 生成新的路径
            i = random.randint(0, len(cities) - 1)
            j = random.randint(0, len(cities) - 1)
            path[i], path[j] = path[j], path[i]

            # 计算新路径的距离
            new_distance = path_length(path, cities)

            # 判断是否接受新路径
            if new_distance < length or random.random() < math.exp((length - new_distance) / temperature):
                best_path = list(path)
                length = new_distance
            else:
                path[i], path[j] = path[j], path[i]  # 恢复原来的路径

        temperature *= cooling_rate  # 降低温度

    return best_path, length

if __name__ == '__main__':
    distance_x = [
        178, 272, 176, 171, 650, 499, 267, 703, 408, 437, 491, 74, 532,
        416, 626, 42, 271, 359, 163, 508, 229, 576, 147, 560, 35, 714,
        757, 517, 64, 314, 675, 690, 391, 628, 87, 240, 705, 699, 258,
        428, 614, 36, 360, 482, 666, 597, 209, 201, 492, 294]
    distance_y = [
        170, 395, 198, 151, 242, 556, 57, 401, 305, 421, 267, 105, 525,
        381, 244, 330, 395, 169, 141, 380, 153, 442, 528, 329, 232, 48,
        498, 265, 343, 120, 165, 50, 433, 63, 491, 275, 348, 222, 288,
        490, 213, 524, 244, 114, 104, 552, 70, 425, 227, 331]

    cities = list(zip(distance_x, distance_y))

    best_path, best_distance = simulated_annealing(cities, 1000, 0.99)

    print("Best Path:", best_path)
    print("Best Distance:", best_distance)